Partition functions of discrete coalescents: from Cayley's formula to Frieze's \zeta(3) limit theorem

摘要

In these expository notes, we describe some features of the multiplicativecoalescent and its connection with random graphs and minimum spanning trees. Weuse Pitman's proof of Cayley's formula, which proceeds via a calculation of thepartition function of the additive coalescent, as motivation and as alaunchpad. We define a random variable which may reasonably be called theempirical partition function of the multiplicative coalescent, and show thatits typical value is exponentially smaller than its expected value. Ourarguments lead us to an analysis of the susceptibility of the Erd\H{o}s-R\'enyirandom graph process, and thence to a novel proof of Frieze's \zeta(3)-limittheorem for the weight of a random minimum spanning tree.